In digital communications, Reed-Solomon (RS) encoders and decoders are used for detecting and correcting errors in digital data transmission. In an RS encoder, check bits are added to the data bits being transmitted to create a data block that is comprised of a number of symbols. Each symbol is comprised of a predetermined number of bits, and each block is comprised of a predetermined number of symbols. An RS decoder, upon receiving a data block, examines the symbols to determine if there are any errors within the data bits and, if so, corrects those errors.
RS decoders use polynomials in the error detection and correction process. FIG. 1 shows a typical structural relationship between an RS decoder 102 and a polynomial expander 104. The RS decoder extracts n roots of an erasure polynomial from a received data block and provides the roots to the expander 104. With these roots, the expander generates an nth order erasure polynomial with coefficients k0, k1, . . . , kn-1, kn that may be expressed as follows:knXn+kn-1Xn-1+ . . . k1X+k0 The expander 104 then provides these coefficients to the decoder 102 for detecting and correcting errors in the received data bits.
FIG. 2 shows a common implementation of the polynomial expander 104, in this instance for generating a third order polynomial. A data storage device 106 stores three roots a, b, and c received from RS decoder 102, each of the roots being expressed as a symbol within the received data block. Within the expander 104, a number of coefficient generators 108–114 generate from these roots respective coefficients for each polynomial term. The result is the following polynomial:X3+(a+b+c)X2+(ac+bc+ab)X+abcEach of the coefficient generators except generator 108 includes adders and/or multipliers. Generator 110 uses two adders 116 and 118 to generate the coefficient (a+b+c); generator 112 uses adders 120 and 122 and multipliers 124, 126, and 128 to generate the coefficient (ac+bc+ab); and generator 114 employs multipliers 130 and 132 to generate the coefficient (abc).
One disadvantage of present polynomial expander designs such as this is that the number of adders and multipliers required to generate the coefficients increases substantially as the order of the polynomial increases. FIG. 2 shows the expander structure for generating a third order polynomial. However, RS decoders commonly require polynomial expanders for generating up to a 16th order polynomial. The additional adders and multipliers for generating such high order polynomials require significant chip area and power when fabricated in an integrated circuit.
Another disadvantage of such polynomial expander designs is the delay in generating the coefficients. The coefficient generators within the expander 104 cannot begin their tasks until the data storage device 106 has received all of the roots from the RS decoder 102. This in turn delays the RS decoder in its detection and correction of errors in the received data bits.
Thus, a mechanism is desired for generating the coefficients of the nth order polynomial given the n-roots of the polynomial with a minimized number of adders and multipliers, and with minimized delay from start of generation of the roots of the polynomial.